//class Solution {
//public:
//    bool wordBreak(string s, vector<string>& wordDict) {
//        unordered_map<string, bool> hash;
//        for (auto& str : wordDict)
//            hash[str] = true;
//        int n = s.size();
//        s = " " + s;
//
//        vector<int> dp(n + 1);
//        dp[0] = true;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = i; j >= 1; j--)
//            {
//                if (hash[s.substr(j, i - j + 1)] && dp[j - 1])
//                {
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//        return dp[n];
//    }
//};



//class Solution {
//public:
//    int longestCommonSubsequence(string text1, string text2) {
//        int m = text1.size(), n = text2.size();
//        text1 = ' ' + text1, text2 = ' ' + text2;
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                if (text1[i] == text2[j])
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                else
//                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//            }
//        }
//        return dp[m][n];
//    }
//};



class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        slow = nums[0], fast = nums[fast];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }
};